#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: title20.py 
@version:
@time: 2023/05/14
https://leetcode.cn/problems/combinations/submissions/
当n = 4. k = 4 时第一层递归从1开始（从2， 3， 4开始均没有意义），
第二层遍历从3开始便都没有意义。则说明本题优化的地方在于每一层遍历应从何处开始。
本题的优化方案之一：
1.已知已选取的数字个数为len(path);
2.则可知还需选取的数字个数为 (k - len(path));
3.在集合n中至多要从该起始位置: (n - (k - len(path)) + 1) 开始遍历

作者：yi-ran-yi-bao-zha-23
链接：https://leetcode.cn/problems/combinations/solution/77-zu-he-by-yi-ran-yi-bao-zha-23-a4xy/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
from typing import List


class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        path = []

        def backtracking(n, k, startIndex):
            if k == len(path):
                result.append(path[:])
                return
            for i in range(startIndex, n - (k - len(path)) + 2):
                path.append(i)
                backtracking(n, k, i + 1)
                path.pop()  # 这里是pop掉上个路径中已经添加的元素，比如下面3选择2以后，再选1，需要把之前选择的2pop掉
                """
                    比如三个数中选三个数
                        []
                     /  |  \
                    3   2   1
                    /\
                (3,2) (3,1)
                /
             (3,2,1)
                """

        backtracking(n, k, 1)
        return result


class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        path = []

        def dfs(i: int) -> None:
            d = k - len(path)  # 还要选 d 个数
            if d == 0:
                ans.append(path.copy())
                return
            for j in range(i, d - 1, -1):
                path.append(j)
                dfs(j - 1)
                path.pop()  # 这里是pop掉上个路径中已经添加的元素，比如下面3选择2以后，再选1，需要把之前选择的2pop掉
                # 或者说最开始选择3以后，当选择2时，需要把3pop掉
                """
                    比如三个数中选三个数
                        []
                     /  |  \
                    3   2   1
                    /\
                (3,2) (3,1)
                /
             (3,2,1)
                """

        dfs(n)
        return ans


# class Solution:
#     def combine(self, n: int, k: int) -> List[List[int]]:
#         return list(itertools.combinations(range(1,n+1),k))
print(Solution().combine(4, 2))


class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        path = []

        def dfs(n):
            d = k - len(path)
            if d == 0:
                ans.append(path[:])
                return
            for i in range(n, d - 1, -1):
                path.append(i)
                dfs(i - 1)
                path.pop()

        dfs(n)
        return ans


print(Solution().combine(4, 2))
